/**
 * 第一种插入排序，用了递归，递归用于每次基数和前面的数字交换后，再用新的基数和它前面的数字继续比较。每次都要进行一个交换动作。
 * 可以更优化点，就是基数每次和前面的数进行比较，如果比前面的数字小，继续和更前面的数字比较，直到遇到基数比前面大的情况再停止比较，交换一次即可。
 * 同样可以看这个网站的演示动画 https://visualgo.net/zh/sorting 结合理解
 */
package com.test.sort;

import java.util.Arrays;

public class InsertionSort2 {
    public static void main(String[] args) {
        int[] a = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        swap(a);
        System.out.println(Arrays.toString(a));
    }
    public static void swap(int[] arr) {
        for (int i = 0; i < arr.length; i++) {  //每轮循环选出一个基数下标，抽一张牌
            int j = i - 1;  //声明当前基数的前一个下标
            int temp = arr[i];  //把当前基数的值赋值给临时变量
            while(j >=0 && temp < arr[j]) {  //判断当前基数如果比前一个数字小，while循环更优雅些
                arr[j+1] = arr[j]; //就把前一个数字往后移动一位，如果继续循环，继续把更前面的数字往后移动
                j--;  //基数还没找到比自己小的数字，继续对比更前一位的数字。要对比的下标继续往前移
            }
            arr[j+1] = temp;  //从while循环出来时，表示已经找到了比基数小的数字，停止后移数字，把基数放在当前位置
            System.out.println(Arrays.toString(arr));
        }
    }
}
